package com.zy.recursion;

/**
 * @description: 实现 pow(x, n) ，即计算 x 的 n 次幂函数。
 * @author: zhaoyi
 * @create: 2019-09-08 15:09
 **/

public class Pow {


    /**
     * 基础解法 java 不会自己优化尾递归 StackOverflowError 风险
     * bug n 是可以为负数的负数会报错
     */
   /* public double myPow(double x, int n) {
        if (n > 0) {
            return x * myPow(x, n - 1);
        } else {
            return 1;
        }
    }*/

    /**
     * 快速幂算法（递归）
     * https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode/
     */
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }

    private double fastPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }


    /**
     * 循环解法， 没有折半优化参考上面的递归fastPow
     * @param x
     * @param n
     * @return
     */
    public double myPow2(double x, int n) {
        double result = x;
        boolean is = false;
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            n = -n;
            is = true;
        }
        while (n > 1) {
            result = result * x;
            n--;
        }
        if (is) {
            return 1 / result;
        } else {
            return result;
        }
    }


}
